Le TD propose plusieurs activités autour des labyrinthes rectangulaires parfaits. Une première partie théorique présente ces notions et étudie la terminaison et la correction d'un algorithme de génération de labyrinthes. la seonde partie propose de modéliser ces labyrinthes en Python dans un paradigme de programmation objet puis d'implémenter l'algorithme de la première partie au travers d'exercices guidés. Enfin la troisième partie s'intéresse à la visualisation des labyrinthes générés, en 2D (Python) puis en 3D (JavaScript). La narration de l'énoncé fait s'entrecroiser les deux premières partie à mesure que les notions sont introduites. Pourtant elles peuvent (et doivent) être traitées séparément.
La première partie étudiant l'algorithme nécessite d'être familiarisé aux preuves en algorithmique. Les structures manipulées et les algorithmes restent relativement simples. Dans l'exercice 6, on aborde la complexité en dénombrant les étapes de l'algorithme. L'exercice 5 propose de prouver la correction par une récurrence forte. Il est tout à fait possible de préférer d'utiliser la notion d'arbre de chemins parcourus ou de rester plus informel.
La deuxième partie utilise une pile et des dictionnaires. Il est important d'avoir déjà rencontré ces notions pour ne pas multiplier les difficultés dans un contexte de découverte de la programmation objet. Les élèves risquent de rencontrer un certain nombre de problèmes de bords.
la troisième partie demande peu de connaissances préalables. La visualisation 2D des labyrinthes utilise superficiellement la librairie matplotlib pour tracer des segments. La visualisation 3D nécessite d'être familiarisé avec la syntaxe des commandes de base en JavaScript.
- Preuve algorithmique, dénombrement, terminaison et correction.
- Découverte de la programmation objet, vocabulaire, définition d'une classe, attributs et méthodes.
- Modélisation d'une situation, choix de représentation
- Utilisation de listes, piles, tableaux et dictionnaires
- Réalisation de solutions algorithmiques dans un contexte pratique
- Encourager une réflexion préalable déconnectée
Extraits du BO :
| Contenus | Capacités attendues |
|---|---|
| Listes, piles, files. Dictionnaires, index et clé. | Choisir une structure de données adaptée à la situation à modéliser. |
| Vocabulaire de la programmation objet:classes, attributs, méthodes, objets. | Écrire la définition d’une classe.Accéder aux attributs et méthodes d’une classe |
| Mise au point des programmes.Gestion des bugs. | Dans lapratique de laprogrammation, savoir répondre aux causes typiques de bugs : effets de bord non désirés, débordements dans les tableaux, instruction conditionnelle non exhaustive... |
| Utilisation de bibliothèques | Utiliser la documentation d’une bibliothèque. |
| Terminaison, correction, coût (1ère) | Il est nécessaire de montrer l’intérêt de prouver la correction d’un algorithme, notamment en mobilisant la notion d’invariant sur des exemples simples. |
Lors de la première partie, déconnectée, l'enseignant commencera par présenter les aspects théoriques des labyrinthes. Le problème de la génération d'un labyrinthe parfait doit faire l'objet d'une discussion avec les élèves puis d'une recherche individuelle ou en binôme. Si besoin, orienter les élèves vers une solution consistant à retirer des murs plutôt que d'en ajouter. Une fois l'algorithme (même vaguement mis en place), on proposera les exercices 1 (dénombrement), 5 (terminaison, correction) et 6 (complexité). On peut éventuellement commencer à réfléchir à des structures de données adaptées. Idéalement, cette partie devrait prendre une heure, mais peut empiéter sur la séance suivante.
La deuxième partie se déroule en salle informatique. Les élèves peuvent travailler seuls ou en binômes. Encourager les élèves à utiliser la méthode print() pour visualiser les étapes de leur programme et avoir une meilleure compréhension de leurs erreurs. Attention aux copier-coller depuis le navigateur web dans l'éditeur Python qui provoque souvent des problèmes d'indentation. Cette partie peut durer 1 ou 2h. Si une solution de génération par exploration est envisagée par un élève c'est l'occasion de faire une comparaison des algorithmes (difficultés rencontrées, structures utilisées) et de la qualité des labyrinthes produits (difficulté de résolution, longueurs des chemins,...). Dans la correction, on choisit de donner 4 murs à une cellule du labyrinthe (N,E,S,W). On peut choisir de n'en retenir que 2 pour éviter les redondances et les contradictions avec les cellules voisines. Si des choix de représentation différents sont faits, il faudra notamment adapter la fonction print() donnée dans l'énoncé.
La troisième partie peut faire suite à la deuxième lors d'une séance supplémentaire ou dés la réalisation des objectifs atteints par l'élève. La difficulté principale est celle de l'orientation de l'axe des ordonnées qui nécessite un changement de variable. Le même problème se présente à nouveau en 3 dimensions. La transition entre Python et JavaScript pourra poser quelques petits problèmes d'adaptation de la syntaxe.
- Un environnement de développement Python avec les librairies matplotlib, random et éventuellement numpy.
- Un navigateur récent (Firefox, Chrome, Edge, pas testé sur Safari). A noter que la scène 3D tourne (beaucoup) mieux sous Chrome... :/
- Un éditeur de texte basique (Notepad++, Scite, Bracket, Sublime Text, etc.) pour la partie JavaScript
- En collaboration avec une classe de la filière STI2D, proposer d'imprimer une combinaison des labyrinthes générés par les élèves de NSI afin de créer un labyrinthe 3D
-
A l'aide de la bibliothèque JavaScript (ou avec un autre moteur), réaliser le même "labyrinthe combiné" qui pourra constituer une aide virtuelle à la résolution.
- Générer des labyrinthes de formes différentes (circulaires, hexagonaux,...)
-
Adapter le programme pour créer un générateur de niveaux pour un jeu-vidéo de type Rogue avec des pièces connectées par différents couloirs.
-
Le travail réalisé peut être réutilisé pour le chapitre abordant l'algorithmique sur les graphes, les parcours et recherches de chemins.
